package oj_leetcode;

public class WildcardMatching {

    public static void main(String[] args) {
        System.out.println(new WildcardMatching().isMatch("", ""));
    }

    public boolean isMatch(String s, String p) {
        int sl = s.length();
        int pl = p.length();
        boolean[][] dp = new boolean[pl][sl];
        boolean[][] used = new boolean[pl][sl];
        return isMatch(s, p, 0, 0, dp, used);
    }

    public boolean isMatch(String s, String p, int j, int i, boolean[][] dp, boolean[][] used) {
        while (i < p.length() && j < s.length()) {
            if (p.charAt(i) == '?') {
                i++;
                j++;
                continue;
            }
            if (p.charAt(i) != '*') {
                if (s.charAt(j) == p.charAt(i)) {
                    i++;
                    j++;
                    continue;
                } else {
                    return false;
                }
            }
            // 是通配符，将连续通配符消去
            while (i < p.length() && p.charAt(i) == '*') {
                i++;
            }
            if (i == p.length()) {
                return true;
            }
            for (; j < s.length(); j++) {
                if (s.charAt(j) == p.charAt(i)) {
                    if (used[i][j]) {
                        if (dp[i][j]) {
                            return true;
                        }
                    } else {
                        dp[i][j] = isMatch(s, p, j, i, dp, used);
                        used[i][j] = true;
                        if (dp[i][j]) {
                            return true;
                        }
                    }
                }
            }
            return false;
        }
        if (i == p.length() && j == s.length()) {
            return true;
        } else {
            return false;
        }
    }
}
